#include <string.h>
#include <type.h>
#include "fs.h"
#include "errno.h"
#include "cache.h"
#include "process.h"

int errno;

static struct cache *cp_sb;
static struct super_block *super;
static struct cache *map_i_blk[10];
static struct cache *map_d_blk[30];

/* ============================================================ */
/*		block and inode operations			*/
/* ============================================================ */

static u32_t map_alloc(u32_t nr, int nr_maps, struct cache **map)
{
	int i, j, k;
	u8_t *p;

	/* Search. */
	for (i = 0; i < nr_maps; i++) {
		p = map[i]->buf;
		for (j = 0; j < SIZE_BLOCK; j++) {
			if (p[j] != 0xFF)
				goto find;
		}
	}
	/* Not find a free node. */
	return 0;
find:
	for (k = 0; k < 8; k++) {
		if (((p[j] >> (7-k)) & 1) == 0)
			break;
	}

	/* Update map. */
	p[j] |= 1 << (7-k);
	map[i]->dirty = 1;

	return i * SIZE_BLOCK * 8 + j * 8 + k;
}
static void map_free(u32_t nr, struct cache **map)
{
	int i = nr / (SIZE_BLOCK * 8);
	int j = (nr % (SIZE_BLOCK * 8)) / 8;
	int k = nr % 8;

	map[i]->buf[j] &= ~(1 << (7-k));
	map[i]->dirty = 1;
}
static u32_t alloc_d_blk(u32_t bn)
{
	u32_t ret;
	ret = map_alloc(bn, super->dmap_blks, map_d_blk);
	super->free_d_blks--;
	cp_sb->dirty = 1;
	return ret + super->begin_dblk;
}
static void free_d_blk(u32_t bn)
{
	map_free(bn - super->begin_dblk, map_d_blk);
	super->free_d_blks++;
	cp_sb->dirty = 1;
}
static u32_t alloc_inode(u32_t in)
{
	u32_t ret;
	ret = map_alloc(in, super->imap_blks, map_i_blk);
	super->free_inodes--;
	cp_sb->dirty = 1;
	return ret + super->begin_iblk * INODE_BLK;
}
static void free_inode(u32_t in)
{
	map_free(in - super->begin_iblk * INODE_BLK, map_i_blk);
	super->free_inodes++;
	cp_sb->dirty = 1;
}

static struct inode *get_inode(u32_t in, int flag)
{
	struct cache *cp;

	/* If passing @flag, we have to make sure that, there is no other
	 * inode in the same block. It's too complex, so we just pass
	 * 0 here for simple. */
	cp = get_block(in / INODE_BLK, 0);
	return &(((struct inode*)(cp->buf))[in % INODE_BLK]);
}

/* Mark the inode dirty. */
static void dirty_inode(u32_t in)
{
	struct cache *cp = get_block(in / INODE_BLK, 0);
	release_block(cp, 1);
}

static void release_inode(u32_t in, int dirty)
{
	struct cache *cp = get_block(in / INODE_BLK, 0);
	release_block(cp, dirty);
	release_block(cp, 0);
}

/* Maybe there should be get/release/free/alloc_entry()s
static struct entry *get_entry(struct inode *dir, int n)
{
}*/


/* ============================================================ */
/*			internal utilities			*/
/* ============================================================ */

/* Split the last part by '/'.
 * Note: the path's last char *should* not be '/'.
 * Return the last part's pointer.
 */
static inline char *split_last(const char *path)
{
	char *p = strrchr(path, '/');
	return p ? p+1 : path;
}

/* Search the file with filename @fname, under directory with
 * inode number @parent.
 * Return the file's inode number. Return 0 if not find.
 */
static u32_t search_file(u32_t parent, const char *fname)
{
	struct inode *pinode;
	struct cache *cache;
	struct entry *entry;
	u32_t ret;
	int i, j;

	pinode = get_inode(parent, 0);
	if(pinode->type != FT_DIR) {
		errno = ENOTDIR;
		ret = NULL;
		goto out;
	}
	for(i = 0; i < ADD_TAIL(pinode->size, ENTRY_BLK); i++) {
		cache = get_block(pinode->i_zones[i], 0);
		entry = (struct entry *)cache->buf;
		for(j = 0; j < MIN(pinode->size - ENTRY_BLK * i, ENTRY_BLK); j++) {
			if(strcmp(entry->name, fname) == 0) {
				ret = entry->inode_nr;
				release_block(cache, 0);
				goto out;
			}
			entry++;
		}
		release_block(cache, 0);
	}
	errno = ENOENT;
	ret = NULL;

out:
	release_inode(parent, 0);
	return ret;
}

u32_t root_inode = 1;
/* Search file by @path_arg.
 * Return the file's inode number. Return NULL if not find.
 * @parent_nr: if the directory of path is found, @parent_nr
 * brings back the parent's inode number; or it will be NULL.
 *
 */
static u32_t search(const char *path_arg, u32_t *parent_nr)
{
	char path[LEN_FILENAME];
	char *pdir, *pnext;
	u32_t pinode, tmp;

	strcpy(path, path_arg);

	/* The begin inode. */
	if(path_arg[0] == '/') {
		pinode = root_inode;
		pdir = path + 1;
	} else {
		pinode = current->work_dir;
		pdir = path;
	}

	/* Do searching. */
	while(pdir[0]) {
		/* @pinode is parent's inode number;
		 * @pdir is the current directory;
		 * @pnext is the remain path. */
		pnext = strchr(pdir, '/');
		if(pnext)
			*(pnext++) = '\0';
		else
			pnext = pdir + strlen(pdir);
		tmp = pinode;
		pinode = search_file(pinode, pdir);

		/* Not found. */
		if(pinode == NULL)
			break;

		pdir = pnext;
	}
	if(parent_nr)
		*parent_nr = pnext[0] ? NULL : tmp;
	return pinode;
}

/* Delete a file's data and inode. */
static void del_data(u32_t inode_nr)
{
	struct inode *inode;
	int i;

	inode = get_inode(inode_nr, 0);
	for(i = 0; i < ADD_TAIL(inode->size, SIZE_BLOCK); i++)
		free_d_blk(inode->i_zones[i]);
	release_inode(inode_nr, 0);
	free_inode(inode_nr);
}

/* Delete an entry from @parent's data. */
static void del_entry(u32_t parent, const char *fname)
{
	struct inode *pinode;
	struct cache *cache, *cache_last;
	struct entry *entry, *entry_last;
	int i, j;
	int ii, jj;

	pinode = get_inode(parent, 0);
	ii = pinode->size / ENTRY_BLK;
	jj = pinode->size % ENTRY_BLK;

	/* Get the file entry's position. */
	for(i = 0; i < ADD_TAIL(pinode->size, ENTRY_BLK); i++) {
		cache = get_block(pinode->i_zones[i], 0);
		entry = (struct entry *)cache->buf;
		for(j = 0; j < MIN(pinode->size - ENTRY_BLK * i, ENTRY_BLK); j++) {
			if(strcmp(entry->name, fname) == 0)
				break;
			entry++;
		}
		release_block(cache, 0);
	}

	/* If this file is not the last one, move the last entry
	 * to its place. */
	if(i * ENTRY_BLK + j != pinode->size - 1) {
		cache_last = get_block(pinode->i_zones[ii], 0);
		entry_last = &(((struct entry *)cache_last->buf)[jj - 1]);
		*entry = *entry_last;
		release_block(cache_last, 0);
	}

	/* If there is a free data block, free it. */
	if(jj == 1)
		free_d_blk(pinode->i_zones[ii]);

	/* Update the parent's inode and data. */
	pinode->size--;
	pinode->m_time = gettime();
	release_block(cache, 1);
	release_inode(parent, 1);
}
static int add_openfile(u32_t inode_nr, int oflag)
{
/* Add this file to the current process's open file table. */
	int i;

	for(i = 0; i < NUM_OPENFILE; i++) {
		if(current->openf[i].inode_pt == NULL)
			break;
	}
	if(i == NUM_OPENFILE)
		return EMFILE;

	current->openf[i].inode_pt = get_inode(inode_nr, 0);
	current->openf[i].inode_nr = inode_nr;
	current->openf[i].pos = 0;
	current->openf[i].oflag = oflag;
	return i;
}

static int mk_dot(u32_t dir_nr, u32_t parent_nr, u32_t bn)
{
	struct inode *file;
	struct entry *entry;
	struct cache *cache;

	file = get_inode(dir_nr, 0);

	bn = alloc_d_blk(bn);
	cache = get_block(bn, 1);
	entry = &(((struct entry *)(cache->buf))[0]);
	strcpy(entry[0].name, ".");
	entry[0].inode_nr = dir_nr;
	strcpy(entry[1].name, "..");
	entry[1].inode_nr = parent_nr;
	file->i_zones[0] = bn;
	file->size = 2;
	release_block(cache, 1);
	return 0;
}

static u32_t create(u32_t parent_nr, const char *fname, u32_t type)
{
	struct inode *file, *parent;
	struct entry *entry;
	struct cache *cp;
	u32_t file_nr, bn;
	time_t t = gettime();
	int i, j;

	/* Set inode. */
	file_nr = alloc_inode(parent_nr);
	file = get_inode(file_nr, 1);

	file->uid = 0;
	file->gid = 0;
	file->type = type;
	file->mode = (type == FT_DIR) ?
		(FM_READ | FM_WRITE | FM_EXEC)
		: (FM_READ | FM_WRITE);
	file->c_time = t;
	file->m_time = t;
	file->a_time = t;
	file->size = 0;
	file->nlinks = 1;

	release_inode(file_nr, 1);

	/* Add entry into parent's data. */
	parent = get_inode(parent_nr, 0);
	i = parent->size / ENTRY_BLK;
	j = parent->size % ENTRY_BLK;
	if(j == 0) {
		bn = alloc_d_blk(i == 0 ? 0 : parent->i_zones[i - 1]);
		parent->i_zones[i] = bn;
		cp = get_block(bn, 1);
	} else {
		bn = parent->i_zones[i];
		cp = get_block(bn, 0);
	}
	entry = &(((struct entry *)(cp->buf))[j]);
	strcpy(entry->name, fname);
	entry->inode_nr = file_nr;
	release_block(cp, 1);

	/* Create the dot and dot-dot directory. */
	if(type == FT_DIR)
		mk_dot(file_nr, parent_nr, bn);

	/* Update parent. */
	parent->size++;
	release_inode(parent_nr, 1);

	return file_nr;
}

/* ============================================================ */
/*			read big functions			*/
/* ============================================================ */

int init_fs(void)
{
	int i;

	cp_sb = get_block(0, 0);
	super = (struct super_block *)(cp_sb->buf);

	/* Check magic number. */
	if(super->zero.uid != 0x1985 || super->zero.gid != 0x0305)
		return 1;

	for (i = 0; i < super->imap_blks; i++)
		map_i_blk[i] = get_block(i + 1, 0);

	for (i = 0; i < super->dmap_blks; i++)
		map_d_blk[i] = get_block(i + super->imap_blks + 1, 0);

	return 0;
}

int open(const char *path, int oflag)
{
	u32_t file_inode, dir_inode;
	const char *fname;

	if(path[strlen(path) - 1] == '/')
		return EINVAL;

	file_inode = search(path, &dir_inode);
	if(file_inode == NULL) {
		if(dir_inode && (oflag & OF_WRITE)) {
			/* Not exist, create it if needed. */
			fname = split_last(path);
			file_inode = create(dir_inode, fname, FT_FILE);
			if(file_inode == NULL)
				return errno;
		} else {
			return errno;
		}
	}
	return add_openfile(file_inode, oflag);
}

int remove(const char *path)
{
	u32_t file_inode, dir_inode;
	u16_t type;
	const char *fname;
	struct inode *inode;

	if(path[strlen(path) - 1] == '/')
		return EINVAL;

	file_inode = search(path, &dir_inode);
	if(file_inode == NULL)
		return errno;

	inode = get_inode(file_inode, 0);
	type = inode->type;
	release_inode(file_inode, 0);
	if(type != FT_FILE)
		return EISDIR;

	del_data(file_inode);
	fname = split_last(path);
	del_entry(dir_inode, fname);
	return 0;
}

int chmod(const char *path, int mode)
{
	u32_t inode_nr;
	struct inode *file;

	inode_nr = search(path, 0);
	if(inode_nr == NULL)
		return errno;

	file = get_inode(inode_nr, 0);
	file->mode = mode;
	release_inode(inode_nr, 1);
	return 0;
}

int lseek(int file, int offset, int flag)
{
	struct openfile *of = &current->openf[file];
	if (of->inode_pt == NULL)
		return EINVAL;
	switch (flag) {
	case SEEK_SET:
		of->pos = offset;
		break;
	case SEEK_CUR:
		of->pos += offset;
		break;
	case SEEK_END:
		of->pos = of->inode_pt->size + offset;
		break;
	default:
		return -1;
	}
	return of->pos;
}

int stat(int i, struct inode *s)
{
	struct openfile *of = &current->openf[i];
	*s = *(of->inode_pt);
	return 0;
}

int read(int file, char *buf, int size)
{
	struct openfile *of = &current->openf[file];
	struct cache *cp;
	int izone, off_blk, off_buf, s;
	u32_t bn;

	if (of->inode_pt == NULL)
		return EINVAL;

	izone = of->pos / SIZE_BLOCK;
	off_blk = of->pos % SIZE_BLOCK;
	off_buf = 0;

	/* Do reading. */
	while (size > 0 && of->pos < of->inode_pt->size) {
		bn = of->inode_pt->i_zones[izone];
		cp = get_block(bn, 0);

		s = MIN(SIZE_BLOCK - off_blk, size);
		s = MIN(of->inode_pt->size - of->pos, s);
		memcpy(buf + off_buf, cp->buf + off_blk, s);

		release_block(cp, 0);
		izone++;
		off_blk = 0;
		off_buf += s;
		size -= s;
		of->pos += s;
	}

	/* Update inode. */
	of->inode_pt->a_time = gettime();
	dirty_inode(of->inode_nr);

	return size;
}

int write(int file, const char *buf, int size)
{
	struct openfile *of = &current->openf[file];
	struct cache *cp;
	int izone, off_blk, off_buf, s;
	int former_zones;
	u32_t bn;

	if (of->inode_pt == NULL)
		return EINVAL;

	former_zones = ADD_TAIL(of->inode_pt->size, SIZE_BLOCK);
	izone = of->pos / SIZE_BLOCK;
	off_blk = of->pos % SIZE_BLOCK;
	off_buf = 0;

	/* Do writing. */
	while (size > 0) {
		if (izone >= former_zones) {
			/* If exceed the file's former size, alloc a block. */
			bn = alloc_d_blk(0);
			of->inode_pt->i_zones[izone] = bn;
			cp = get_block(bn, 1);
		} else {
			/* else, read the block from disk. */
			bn = of->inode_pt->i_zones[izone];
			cp = get_block(bn, 0);
		}

		s = MIN(SIZE_BLOCK - off_blk, size);
		memcpy(cp->buf + off_blk, buf + off_buf, s);

		release_block(cp, 1);
		izone++;
		off_blk = 0;
		off_buf += s;
		size -= s;
		of->pos += s;
	}

	/* Free extra blocks. */
	while (izone < former_zones)
		free_d_blk(of->inode_pt->i_zones[izone++]);

	/* Update inode. */
	of->inode_pt->size = of->pos;
	of->inode_pt->m_time = gettime();
	dirty_inode(of->inode_nr);

	return size;
}

int mkdir(const char *path)
{
	u32_t dir_nr, file_nr;
	const char *fname;

	if(path[strlen(path) - 1] == '/')
		return EINVAL;

	file_nr = search(path, &dir_nr);
	// has exist
	if(file_nr != NULL)
		return EEXIST;

	// no parent
	if(dir_nr == NULL)
		return errno;

	fname = split_last(path);
	file_nr = create(dir_nr, fname, FT_DIR);
	if(file_nr == NULL)
		return errno;

	return 0;
}

int rmdir(const char *path)
{
	u32_t file_inode, dir_inode;
	u16_t type;
	u32_t size;
	const char *fname;
	struct inode *inode;

	if(path[strlen(path) - 1] == '/')
		return EINVAL;

	file_inode = search(path, &dir_inode);
	if(file_inode == NULL)
		return errno;

	inode = get_inode(file_inode, 0);
	type = inode->type;
	size = inode->size;
	release_inode(file_inode, 0);
	if(type != FT_DIR)
		return ENOTDIR;
	if(size != 2)
		return -10;

	del_data(file_inode);
	fname = split_last(path);
	del_entry(dir_inode, fname);
	return 0;
}

int opendir(const char *path)
{
	u32_t dir_nr;
	u16_t type;

	dir_nr = search(path, 0);
	if(dir_nr == NULL)
		return errno;

	type = get_inode(dir_nr, 0)->type;
	release_inode(dir_nr, 0);
	if(type != FT_DIR)
		return ENOTDIR;
	return add_openfile(dir_nr, 0);
}

int readdir(int dir, char *fname)
{
	struct openfile *fp = &current->openf[dir];
	struct entry *entry;
	struct cache *cp;
	int i, j;
	u32_t nr;

	if(fp->inode_pt == NULL)
		return EINVAL;
	if(fp->pos == fp->inode_pt->size)
		return 0;

	i = fp->pos / ENTRY_BLK;
	j = fp->pos % ENTRY_BLK;
	fp->pos++;

	cp = get_block(fp->inode_pt->i_zones[i], 0);
	entry = &(((struct entry *)(cp->buf))[j]);
	strcpy(fname, entry->name);
	release_block(cp, 0);
	return 1;
}

void close(int n)
{
	struct openfile *of = &current->openf[n];
	release_inode(of->inode_nr, 0);
	of->inode_pt = 0;
}


/* ============================================================ */
/*			should not in kernel			*/
/* ============================================================ */

extern u32_t num_sect_disk;
void format(void)
{
	struct cache *sbcp, *cp;
	struct super_block *sb;
	time_t t = gettime();
	int i, maps, rem;

	/* Set super-block. */
	sbcp = get_block(0, 1);
	sb = (struct super_block *)sbcp->buf;

	/* Magic number. */
	sb->zero.uid = 0x1985;
	sb->zero.gid = 0x0305;

	/* Fs information. */
	sb->size_block = SIZE_BLOCK;
	sb->blocks = num_sect_disk / SEC_BLK;

	/* Number of i_blks (blocks that contain inodes). */
	sb->i_blks = ADD_TAIL(sb->blocks, P_INODE_DATA);
	/* Number of inodes. */
	sb->inodes = sb->i_blks * INODE_BLK;
	/* Number of bitmap-blocks for inodes. */
	sb->imap_blks = ADD_TAIL(sb->inodes, SIZE_BLOCK * 8);

	rem = sb->blocks - sb->imap_blks - sb->i_blks - 1;
	/* Number of bitmap-blokcs for d_blks. */
	sb->dmap_blks = ADD_TAIL(rem, SIZE_BLOCK * 8);
	/* Number of d-blks. (blocks that contain data-blks) */
	sb->d_blks = rem - sb->dmap_blks;

	/* The first i_blk and d_blk. */
	sb->begin_iblk = 1 + sb->imap_blks + sb->dmap_blks;
	sb->begin_dblk = sb->begin_iblk + sb->i_blks;

	/* Number of free inodes and d_blks. */
	sb->free_inodes = sb->inodes;
	sb->free_d_blks = sb->d_blks;

	maps = sb->imap_blks + sb->dmap_blks;

	/* Set inode-bitmap and data-bitmap. */
	for(i = 0; i < maps; i++) {
		cp = get_block(i + 1, 1);
		memset(cp->buf, 0, SIZE_BLOCK);
		release_block(cp, 1);
	}

	init_fs();

	/* Inode for root.*/
	sb->root.uid = 0;
	sb->root.gid = 0;
	sb->root.type = FT_DIR;
	sb->root.mode = FM_READ | FM_WRITE | FM_EXEC;
	sb->root.c_time = t;
	sb->root.m_time = t;
	sb->root.a_time = t;
	sb->root.size = 0;
	sb->root.nlinks = 1;
	mk_dot(root_inode, root_inode, 0);

	release_block(sbcp, 1);
}
